package Hot100;

/**
 * @author zhangmin
 * @create 2022-01-10 10:39
 */
public class countBits338 {
    /**
     * 338. 比特位计数
     * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
     * 1、每个数字计算
     * 2、dp+最高有效位：对于正整数 x，如果可以知道最大的正整数 y，使得 y≤x 且 y 是 2 的整数次幂（y & (y−1)=0），则 y 的二进制表示中只有最高位是 1，其余都是 0，
     * 此时称 y 为 x 的「最高有效位」。令 z=x−y，显然 0≤z<x，则 bits[x]=bits[z]+1。
     * 3、dp+最低设置位：定义正整数 x 的「最低设置位」为 x 的二进制表示中的最低的 1 所在位。令 y=x & (x−1)，则 y 为将 x 的最低设置位从 1 变成 0 之后的数，
     * 显然 0≤y<x，bits[x]=bits[y]+1。因此对任意正整数 x，都有 bits[x]=bits[x & (x−1)]+1。
     * */
    public int[] countBits1(int n) {
        int[] bits=new int[n+1];
        int highbit=0;
        for (int i = 1; i <= n; i++) {
            if ((i&(i-1))==0){
                highbit=i;
            }
            bits[i]=bits[i-highbit]+1;
        }
        return bits;
    }
    public int[] countBits(int n) {
        int[] bits=new int[n+1];
        for (int i = 1; i <=n ; i++) {
            bits[i]=bits[i&(i-1)]+1;
        }
        return bits;
    }
}
